//
// Created by xili on 2024/8/30 14:56.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    int twoCitySchedCost(vector <vector<int>> &costs) {
        //默认所有人都去往a地，计算从a地转往b地的代价，让代价最小的n/2个人去往b地
        int n = costs.size();
        vector<int> v(n);
        int ans = 0;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            v[i] = costs[i][1] - costs[i][0];
            sum += costs[i][0];
        }
        sort(v.begin(), v.end());
        for (int i = 0; i <= n / 2; i++) {
            ans += v[i];
        }
        return ans + sum;
    }
};